﻿package zf.data.ds
{
	import zf.data.ds.node.SListNode;

	/**
	 * 环单向链表，包括头指针和尾指针，和 SLinkedList 不同之处在于 环的尾指针的next指向头
	 * @author mike.zhang
	 * @langversion 3.0 
	 * @playerversion Flash 9 
	 * 
	 * @see SLinkedList
	 */
	public class RingSLinkedList extends SLinkedList implements ILinkedList
	{
		/**
		 * 环单向链表 
		 * @param args 链表数据
		 * 
		 */
		public function RingSLinkedList (... args)
		{
			head=tail=null;
			_length=0;
			if (args.length > 0)
			{
				append.apply (this,args);
			}
			//linkHead();
		}
		/**
		 * @inheritDoc
		 * 
		 */
		override public  function toArray ():Array
		{
			cutHead ();
			var arr:Array=super.toArray();
			linkHead ();
			return arr;
		}
		/**
		 * @inheritDoc
		 * 
		 */
		override public  function clear ():void
		{
			cutHead ();
			super.clear ();
		}
		/**
		 * @inheritDoc
		 * 
		 */
		override public  function contains (obj:*):Boolean
		{
			cutHead ();
			var bool:Boolean=super.contains(obj);
			linkHead ();
			return bool;
		}
		/**
		 * 尾指针断开头指针 
		 * 
		 */
		private function cutHead ():void
		{
			if (tail)
			{
				tail.next=null;
			}
		}
		/**
		 * 尾指针连接头指针 
		 * 
		 */
		private function linkHead ():void
		{
			if (head && tail)
			{
				tail.next=head;
			}
		}
		/**
		 * 添加一个或多个数据到链表尾，返回添加的第一个链表节点 
		 * @param args 要添加的一个或多个数据
		 * @return 添加到链表的第一个数据构成的节点
		 * 
		 */
		override public  function append (... args):SListNode
		{
			var l:uint=args.length;
			//var sll:SLinkedList=new SLinkedList(args[0]);
			var node:SListNode=new SListNode(args[0]);
			if (head)
			{
				tail.next=node;
				tail=node;
			}
			else
			{
				head=tail=node;
			}
			//添加一个以上的元素
			if (l > 1)
			{
				var t:SListNode=node;
				for (var i:uint=1; i < l; i++)
				{
					node=new SListNode(args[i]);
					tail.next=node;
					tail=node;
				}
				_length+= l;
				tail.next=head;
				return t;
			}
			//添加一个元素
			_length++;
			tail.next=head;
			return node;
		}
		/**
		 * 连接一个或多个SLinkedList链表，并返回连接成的新链表，本链表保持不变 
		 * @param args 要连接的一个或多个SLinkedList链表
		 * @return 返回一个新的SLinkedList链表
		 * 
		 */
		override public  function concat (... args):SLinkedList
		{
			var rsll:RingSLinkedList=this.cloneR();
			var l:uint=args.length;
			for (var i:uint=0; i < l; i++)
			{
				rsll.append (args[i]);
			}
			return rsll;
		}

		/**
		 * 克隆链表,请注意，因为是覆盖，故而返回只能是 SLinkedList 类型
		 * @return 链表 
		 * 
		 */
		override public  function clone ():SLinkedList
		{
			cutHead ();
			var sll:SLinkedList=super.clone();
			//linkHead();
			return sll;
		}
		/**
		 * 克隆环单向链表
		 * @return 环单向链表 
		 * 
		 */
		public function cloneR ():RingSLinkedList
		{
			if (head)
			{
				return RingSLinkedList.creatRingSLinkedList(this);

			}
			return null;
		}
		/**
		 * 在链表中slp所指向的节点后面插入一个数据为obj的节点 
		 * @param slp 指针，指向链表的节点
		 * @param obj 数据，要生成节点的数据
		 * @return 插入后形成的节点
		 * 
		 */
		override public  function insertAfter (slp:SListPointer,obj:*):SListNode
		{
			cutHead ();
			var node:SListNode=super.insertAfter(slp,obj);
			linkHead ();
			return node;

		}
		/**
		 * 使用全等（===），从form指针指向的节点开始，查找数据为obj的节点，并返回指向obj数据节点的指针。
		 * @param obj 待查找的数据
		 * @param form 查找开始的指针
		 * @return 如果有，返回指向该数据所在节点的指针，否则返回null
		 * 
		 */
		override public  function nodeOf (obj:*,form:SListPointer=null):SListPointer
		{
			cutHead ();
			var sp:SListPointer=super.nodeOf(obj,form);
			linkHead ();
			return sp;
		}

		/**
		 * 删除指针指向的节点 
		 * @param p 指针，指向要删除的节点
		 * @return 删除成功返回true
		 * 
		 */
		override public  function remove (p:SListPointer):Boolean
		{
			cutHead ();
			var bool:Boolean=super.remove(p);
			linkHead ();
			return bool;
		}
		/**
		 * 删除链表中最后一个节点，并返回该节点数据 
		 * @return 数据
		 * 
		 */
		override public  function removeTail ():*
		{
			cutHead ();
			var data:*=super.removeTail();
			linkHead ();
			return data;
		}
		/**
		 * 删除链表中第一个节点，并返回该节点数据 
		 * @return 数据
		 * 
		 */
		override public  function removeHead ():*
		{
			cutHead ();
			var data:*=super.removeTail();
			linkHead ();
			return data;
		}
		/**
		 * 倒转链表操作 
		 * 
		 */
		override public  function reverse ():void
		{
			cutHead ();
			super.reverse ();
			linkHead ();
		}
		/**
		 * @inheritDoc
		 * 
		 */
		override protected  function getPrev (form:SListPointer):SListNode
		{
			if (! form || ! form.node || head == null)
			{
				return null;
			}
			if (form.node == head)
			{
				return tail;
			}
			var node:SListNode=head;
			while (node.next != form.node)
			{
				node=node.next;
				if (! node)
				{
					return null;
				}
			}
			return node;
		}
		/**
		 * 添加或删除链表中的数据，返回一个被删除的节点组成的链表。同时start指针将指向返回的链表的头
		 * @param start 起始指针
		 * @param deleteCount 要操作的节点个数
		 * @param args 数据
		 * @return 被删除节点组成的链表
		 * 
		 */
		override public  function splice (start:SListPointer=null,deleteCount:uint=uint.MAX_VALUE,... args):SLinkedList
		{
			if (start)
			{
				if (start.list != this)
				{
					return null;
				}
			}
			else
			{
				start=creatPointer();
			}
			var l:uint=args.length;
			var h:SListNode=null;
			var t:SListNode=null;

			var s:SListNode;
			var e:SListNode;

			var node:SListNode;

			var sll:SLinkedList;

			var i:uint;

			if (l > 0)
			{
				h=new SListNode(args[0]);
				node=h;
				for (i=1; i < l; i++)
				{
					node.next=new SListNode(args[i]);
					node=node.next;
				}
				t=node;
			}
			if (deleteCount >= _length)
			{
				//删除了全部
				//trace("删除了全部")
				sll=toSLinkedList();
				clear ();
				if (l > 0)
				{
					head=h;
					t.next=h;
					tail=t;
					_length=l;
				}
				return sll;
			}
			var index:uint=getIndex(start);
			s=getPrev(start);
			s.next=null;

			//var s:SListNode=start.node;
			node=start.node;
			var p:SListNode;
			sll=new SLinkedList  ;
			for (i=0; i < deleteCount; i++)
			{
				sll.append (node.data);
				p=node.next;
				node.next=null;
				node=p;
			}
			e=node;
			if (deleteCount + index > _length)
			{
				//删除了头和尾
				//trace("删除了头和尾")
				head=e;
				if (l > 0)
				{
					s.next=h;
					t.next=e;
					tail=t;
				}
				else
				{
					s.next=e;
					tail=s;
				}
			}
			else if (deleteCount + index == _length)
			{
				//删除了尾
				//trace("删除了尾 index:"+index)
				if (l > 0)
				{
					s.next=h;
					t.next=e;//head
					tail=t;
				}
				else
				{
					s.next=e;//head
					tail=s;
				}
			}
			else
			{
				if (index == 0)
				{
					//头被删除
					//trace("头被删除");
					if (l > 0)
					{
						s.next=h;
						t.next=e;
						head=h;
					}
					else
					{
						s.next=e;
						head=e;
					}
				}
				else
				{
					//头和尾均未删除
					//trace("头和尾均未删除")
					if (l > 0)
					{
						s.next=h;
						t.next=e;
					}
					else
					{
						s.next=e;
					}
				}
			}
			var n:int=_length - deleteCount + l;
			_length=n > 0?n:0;

			return sll;
		}
		/**
		 * 返回指针所指向的节点在链表中的下标（从0开始，例如第5个节点下标为4），如果找不到将返回-1 
		 * @param pointer 指针
		 * @return 下标或-1
		 * 
		 */
		private function getIndex (pointer:SListPointer):int
		{

			var node:SListNode=pointer.node;
			var p:SListNode=head.next;
			if (node == head)
			{
				return 0;
			}
			var index:int=1;
			while (p != head)
			{
				if (node == p)
				{
					return index;
				}
				index++;
				p=p.next;
			}
			return -1;
		}
		/**
		 * 返回环链表的描述信息 
		 * @return 格式[数据1,数据2, ...]
		 * 
		 */
		override public  function toString ():String
		{
			if (isEmpty())
			{
				return null;
			}
			var p:SListNode=head.next;
			//var str:String="[(Length:"+_length+" head:"+head+" tail:"+tail+") 0:"+head.toString()+" ";
			//var i:uint=1;
			var str:String="[" + head.toString() + " ";
			while (p != head)
			{
				//str+=i+":"+p.toString()+" ";
				str+= p.toString() + " ";
				p=p.next;
				//i++;
			}
			str+= "]";
			return str;
		}
		/**
		 * 将链表（实现 ILinkedList 接口)转化为环单向链表  
		 * @param l 链表
		 * @return 环单向链表
		 * 
		 */
		public static  function creatRingSLinkedList (l:ILinkedList):RingSLinkedList
		{
			var arr:Array=l.toArray();
			var len:uint=arr.length;
			var rsll:RingSLinkedList=new RingSLinkedList  ;
			for (var i:uint=0; i < len; i++)
			{
				rsll.append (arr[i]);
			}
			return rsll;
		}
		/**
		 * 将环单向链表转化成单向链表(此方法并不会破坏当前的环链表) 
		 * @return 单向链表
		 * @see SLinkedList
		 * 
		 */
		public function toSLinkedList ():SLinkedList
		{
			var sll:SLinkedList=clone();
			//sll.tail.next=null;
			return sll;
		}
	}
}